package com.liner;

import java.util.Arrays;

/**
 * @author 一条淡水鱼 ゆ
 * @Classname QuickSort
 * @Description 快速排序
 * @Date 2023-04-02
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] array = BubbleSort.getInts();
        System.out.println(Arrays.toString(array));

        //quickSort1(array, 0, array.length - 1);
        quickSort2(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }

    private static void quickSort2(int[] array, int start, int end) {
        //使用新的变量表示枢纽元
        int pivot = array[end];
        //使用新变量，表示左侧区域最大下标，默认最左侧
        int x = start;
        //使用新变量，表示右侧区域最小下标，默认最右侧
        int y = end;

        //y会递减，x会递增，且不能交叉
        while (x < y) {
            //从右至左找到每个大于枢纽元的元素，标记，当指向元素小于或等于枢纽元，跳出循环
            while (x < y && array[y] > pivot) {
                y--;
            }


            //从左至右找到每个小于枢纽元的元素，标记，当指向元素大于或等于枢纽元，跳出循环
            while (x < y && array[x] < pivot) {
                x++;
            }

            //判断现在的x与y指向的元素是否与枢纽元大小相同
            if (x < y && array[x] == array[y]) {
                //x与y指向枢纽元大小相等 x++,否则会卡死
                x++;
            } else {
                //x与y指向不是枢纽元，x指向元素大于枢纽元，y指向元素小于枢纽元  则需要换位
                int temp = array[x];
                array[x] = array[y];
                array[y] = temp;
            }

            //如果左侧元素仍有多个元素
            if (x - 1 > start) {
                quickSort2(array, start, x - 1);
            }

            //如果右侧区域仍有多个元素
            if (y + 1 < end) {
                quickSort2(array, y + 1, end);
            }


        }


    }

    private static void quickSort1(int[] array, int start, int end) {

        //枢纽元，初定最后一个元素
        int pivot = array[end];
        //创建一个新的变量，用于最左侧区域的最大下标
        int x = start - 1;
        //遍历数组
        for (int i = start; i < end; i++) {
            //判断当前元素是否小于或等于枢纽元
            if (array[i] <= pivot) {
                //判断当前元素的左侧是否存在大于枢纽元的元素
                if (i - x > 1) {
                    int temp = array[i];
                    array[i] = array[x + 1];
                    array[x + 1] = temp;
                    //x自增
                    x++;
                } else {
                    x = i;
                }


            }

        }

        //将枢纽元放在左右区域之间
        //交换枢纽元与第一个大于枢纽元的位置
        if (pivot < array[x + 1]) {
            array[end] = array[x + 1];
            array[x + 1] = pivot;
        }

        //如果左侧元素仍有多个元素
        if (x > start) {
            quickSort1(array, start, x);
        }

        //如果右侧区域仍有多个元素
        if (end - x - 1 > 1) {
            quickSort1(array, x + 2, end);
        }


    }

}
